package com.java.container;

import java.util.*;

/**
 * @program: java_basic_knowledge
 * @author: CaoYong
 * @create: 2021-04-13 09:58
 * ArrayList的特点：
 * 1. 可以随机访问，按照数组索引进行访问效率高, 为O(1)
 * 2. 除非数组已排序，否则按内容查找元素效率低，为O(n)
 * 3. 添加元素的效率还可以, 添加N个元素的效率为O(n)
 * 4. 插入和删除元素效率比较低,需要移动元素，为O(n)
 **/
public class ArrayListKnowledge {

    /**
     * ArrayList的内部维护一个数组，用于存储数据，一个size记录元素的个数
     * ArrayList的所有操作基本上围绕着这个数组和size展开
     * ArrayList相较于数组的区别就是其是变长的，内部数组elementData会随着实际元素个数的增多而重新分配
     */
    public static class HowToDefineArrayList<E> implements Iterable<E>{

        private Object[] elementData;
        private int size;

        private static final int DEFAULT_CAPACITY = 10; // 定义的ArrayList的数组初始大小
        private static final Object[] EMPTY_ELEMENTDATA = {}; // 定义空数组用于判断数组是否为空

        private int modCount = 0;

        public HowToDefineArrayList() {
            this.elementData = EMPTY_ELEMENTDATA;
        }

        public boolean add(E e) {
            // 如果需要添加一个元素，那么List需要的最小的空间为当前的size+1，有可能因为添加一个元素而越界
            // 所以添加元素前首先需求判断数组大小是否够用
            ensureCapacityInternal(size + 1);
            elementData[size++] = e;
            return true;
        }

        private void ensureCapacityInternal(int minCapacity) {
            // 如果数组为空，首次至少要分配默认值的大小，默认值为10，然后继续minCapacity是否越界
            if(elementData == EMPTY_ELEMENTDATA) {
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            ensureExplicitCapacity(minCapacity);
        }

        private void ensureExplicitCapacity(int minCapacity) {
            modCount++; // 增加修改次数
            // 实际判断minCapacity是否大于数组长度，如果大于则要进行扩容
            if(minCapacity - elementData.length > 0) {
                grow(minCapacity);
            }
        }

        private void grow(int minCapacity) {
            int oldCapacity = elementData.length;
            // 首先将旧容量扩大为1.5倍，再判断扩容后的容量与最新需要的容量的大小，如果还小于minCapacity, 则直接扩容到minCapacity
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity < 0) {
                newCapacity = minCapacity;
            }
            // 扩容后拷贝旧数组的元素到一个新数组，数组长度为扩容的长度
            elementData = Arrays.copyOf(elementData, newCapacity);
        }

        public E remove(int index) {
            // 判断要删除的index是否越界
            rangeCheck(index);
            modCount ++; // 操作数加1
            E oldValue = elementData(index);
            int numMoved = size - index - 1;
            if(numMoved > 0) {
                // 删除前数组下标为index+1后元素从下标index开始复制，复制长度为要移动的元素大小其实就等价于index后的元素前移一位
                System.arraycopy(elementData, index + 1, elementData, index, numMoved);
            }
            elementData[--size] = null; // size减1同时释放对象
            return oldValue;
        }

        private void rangeCheck(int index) {
            if (index >= size) {
                throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
            }
        }

        E elementData(int index) {
            return (E) elementData[index];
        }

        // ArrayList要想能够用for each实现迭代，就要实现Iterable<E>接口， 而这个接口定义了一个返回Iterator迭代器的方法
        // 因此ArrayList内部要实现一个构造Iterator<E>的方法
        @Override
        public Iterator<E> iterator() {
            return new Itr();
        }

        // ArrayList内部定义的迭代器类实现Iterator<E>接口，并实现hasNext(), next()和remove()方法
        private class Itr implements Iterator<E>{
            int cursor; //下一个要返回元素的位置
            int lastRet = -1; // 最后一个返回的索引的位置，如果没有，为-1
            int exceptedModCount = modCount; // 期待的操作数

            Itr() {}

            @Override
            public boolean hasNext() {
                return cursor != size;
            }

            @Override
            public E next() {
                // 先判断当前的操作数与预期操作数是否一致
                checkForComodification();
                int i = cursor; // 将要读取的下标i设置为下一个元素要返回的位置
                if (i >= size) {
                    throw new NoSuchElementException();
                }
                Object[] elementData = HowToDefineArrayList.this.elementData;
                if (i >= elementData.length) {
                    throw new ConcurrentModificationException();
                }
                cursor = i + 1; // cursor后移
                return (E) elementData[lastRet = i]; // 读取i下标的元素并记录最后一个返回索引的位置
            }

            @Override
            public void remove() {
                if(lastRet < 0) {
                    throw new IllegalStateException();
                }
                checkForComodification();
                try {
                    HowToDefineArrayList.this.remove(lastRet); // 删除最后一个返回索引的元素
                    cursor = lastRet; // 将下一个将要访问的元素下标设置为当前最后返回索引元素的下标
                    lastRet = -1; // 最后一个返回索引的元素下标前移
                    exceptedModCount = modCount; // 更新期待的操作数
                } catch (IndexOutOfBoundsException ex) {
                    throw new ConcurrentModificationException();
                }
            }

            private void checkForComodification() {
                if(modCount != exceptedModCount) {
                    throw new ConcurrentModificationException();
                }
            }
        }

    }

    public static void howToUseArrayList() {
        HowToDefineArrayList<Integer> arrayList = new HowToDefineArrayList();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);

        for (Integer integer : arrayList) {
            System.out.println(integer);
        }
    }

    public static void main(String[] args) {
        howToUseArrayList();
    }
}
